package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

/**
 * @author Fengkai
 * @creat 2023/4/24
 * 羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。
 * 要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。
 * 备注：农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。
 * 农夫自身不占用船的容量。
 * 输入描述
 * 第一行输入为M，N，X， 分别代表羊的数量，狼的数量，小船的容量。
 * 输出描述
 * 输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。
 * （若无法满足条件则输出0）
 * 示例1：
 * 输入： 5 3 3
 * 输出： 3
 * 说明： 第一次运2只狼 第二次运3只羊 第三次运2只羊和1只狼
 */
public class TranSpotrSheep {
    public static int result;

    public static void main (String[] args) {
        System.out.println(tranSpotrSheep(5, 4, 1));
    }

    public static int tranSpotrSheep (int m, int n, int x) {
        result = (m + n) * x;
        //对岸的羊  狼
        int anotherM = 0;
        int anotherN = 0;
        dfs(m, n, anotherM, anotherN, x, 0);
        if (result == (m + n) * x) {
            return 0;
        } else {
            return result;
        }
    }

    private static int dfs (int m, int n, int anotherM, int anotherN, int x, int count) {
        //若可以一次性运走，结束了
        if (x >= (m + n)) {
            if (count + 1 < result) {
                result = count + 1;
            }
            return count + 1;
        }
        //尝试运一部分狼一部分羊
        //要上船的羊数量不可以超过岸上数量、也不可以超过船的容量
        for (int i = 1; i <= m; i++) {
            //要上船的狼的数量不可以超过岸上数量、也不可以超过船装了羊后的剩余的容量
            for (int j = 1; j <= n && i + j <= x; j++) {
                if (i + j == 0) {
                    continue;
                }
                //船离岸后，原来这岸，要么没有羊，要么羊比狼多，才可以运；对岸也一样，不考虑回程带动物
                if (((m - i >= n - j) || m - i == 0) && ((anotherM + i >= anotherN + j) || anotherM + i == 0)) {
                    int dfs = dfs(m - i, n - j, anotherM + i, anotherN + j, x, count + 1);
                    if (dfs != 0 && dfs < result) {
                        result = dfs;
                    }
                }
            }
        }
        return 0;
    }
}
